#include "MyLinkedList.h"
#include <stdio.h>
#include <stdlib.h>

/**
 * 创建一个节点
 * @param data 要存入的数据
 * @return 返回一个struct Node *指针
 */
struct Node * Node_init(int data) {
    struct Node * p_node = (struct Node *) malloc(sizeof(struct Node));
    if (!p_node) {
        perror("Node_init failure.");
        return NULL; //这里不能直接结束，而是需要让调用方知道内存分配失败了，需要调用方将所有的节点都释放之后再退出
    }
    p_node -> data = data;
    p_node -> next = NULL;
    return p_node;
}

/**
 * 释放创建的节点
 * @param p_node 待释放的节点
 */
void Node_deinit(struct Node * p_node) {
    if (!p_node -> next) {
        free(p_node -> next);
        p_node -> next = NULL;
    }
    free(p_node);
    p_node = NULL;
}

/**
 * 创建一个链表
 * @return 返回一个struct MyLinkedList *指针
 */
struct MyLinkedList * MyLinkedList_init() {
    struct MyLinkedList * p_link = (struct MyLinkedList *) malloc(sizeof(struct MyLinkedList));
    if (!p_link) {
        perror("MyLinkedList_init failure.");
        exit(EXIT_FAILURE);
    }
    p_link -> head = NULL;
    p_link -> last = NULL;
    p_link -> size = 0;
    return p_link;
}

/**
 * 释放创建的链表
 * @param p_link 待释放的链表
 */
void MyLinkedList_deinit(struct MyLinkedList * p_link) {
    int index = 0;
    for (index = p_link -> size - 1; index >= 0; --index) {
        struct Node * p_node = MyLinkedList_remove(p_link, index);
        Node_deinit(p_node);
    }
    free(p_link);
    p_link = NULL;
}

/**
 * 链表查找元素
 * @param p_link 待查找节点的链表
 * @param index 查找的位置
 * @return 查找到的节点
 */
struct Node * MyLinkedList_get(struct MyLinkedList * p_link, int index) {
    int idx = 0;
    if (index < 0 || index >= p_link -> size) {
        fprintf(stderr, "%s Out of the link actual element range %d.\n", __func__, index);
        MyLinkedList_deinit(p_link);
        exit(EXIT_FAILURE);
    }
    struct Node * tmp = p_link -> head;
    for (; idx < index; ++idx) {
        tmp = tmp -> next;
    }
    return tmp;
}

/**
 * 链表插入元素
 * @param p_link 待插入元素的链表
 * @param data 插入元素
 * @param index 插入位置
 */
void MyLinkedList_insert(struct MyLinkedList * p_link, int data, int index) {
    if (index < 0 || index > p_link -> size) {
        fprintf(stderr, "%s Out of the link actual element range %d.\n", __func__, index);
        MyLinkedList_deinit(p_link);
        exit(EXIT_FAILURE);
    }
    struct Node * p_insertedNode = Node_init(data);
    if (!p_insertedNode) {
        MyLinkedList_deinit(p_link);
        exit(EXIT_FAILURE);
    }
    if (0 == p_link -> size) {
        //空链表
        p_link -> head = p_insertedNode;
        p_link -> last = p_insertedNode;
    } else if (0 == index) {
        //插入头部
        p_insertedNode -> next = p_link -> head;
        p_link -> head = p_insertedNode;
    } else if (index == p_link -> size) {
        //插入尾部
        p_link -> last -> next = p_insertedNode;
        p_link -> last = p_insertedNode;
    } else {
        //插入中间
        struct Node * p_prevNode = MyLinkedList_get(p_link, index - 1);
        p_insertedNode -> next = p_prevNode -> next;
        p_prevNode -> next = p_insertedNode;
    }
    ++(p_link -> size);
}

/**
 * 链表删除元素（调用方注意记得释放被删除的元素）
 * @param p_link 待删除元素的链表
 * @param index 被删除的位置
 * @return 被删除的节点
 */
struct Node * MyLinkedList_remove(struct MyLinkedList * p_link, int index) {
    if (index < 0 || index >= p_link -> size) {
        fprintf(stderr, "%s Out of the link actual element range %d.\n", __func__, index);
        MyLinkedList_deinit(p_link);
        exit(EXIT_FAILURE);
    }
    struct Node * p_removeNode = NULL;
    if (0 == index) {
        //删除头节点
        p_removeNode = p_link -> head;
        p_link -> head = p_link -> head -> next;
    } else if (p_link -> size - 1 == index) {
        //删除尾节点
        struct Node * p_prevNode = MyLinkedList_get(p_link, index - 1);
        p_removeNode = p_prevNode -> next;
        p_prevNode -> next = NULL;
        p_link -> last = p_prevNode;
    } else {
        //删除中间节点
        struct Node * p_prevNode = MyLinkedList_get(p_link, index - 1);
        struct Node * p_nextNode = p_prevNode -> next -> next;
        p_removeNode = p_prevNode -> next;
        p_prevNode -> next = p_nextNode;
    }
    --(p_link -> size);
    return p_removeNode;
}

/**
 * 输出链表
 * @param p_link 待输出的链表
 */
void MyLinkedList_output(struct MyLinkedList * p_link) {
    struct Node * tmp = p_link -> head;
    printf("[");
    while (tmp) {
        printf("%d", tmp -> data);
        tmp = tmp -> next;
        if (tmp) {
            printf(", ");
        }        
    }
    printf("]\n");
}
